package com.huawei.controller;


/**
 * description
 *
 * @author cwx1134046
 * @since 2023-01-29
 */
public class CountRangeSum {

    public  int countRangeSum(int[] nums, int lower, int upper) {
        long[] sums = new long[nums.length + 1];
        long sum = 0;
        for (int i = 0; i<nums.length+1 ;i++ ){
            if(i != 0) {
                sum = sum + nums[i-1];
            }
            sums[i] = sum;
        }
        return  countRange(sums, lower, upper, 0, sums.length - 1);
    }

    public  int countRange(long[] nums,int lower,int upper,int left,int right){
        if(left == right){
            return 0;
        }else {
            int mid = (left+right)/2;
            int leftCount = countRange(nums,lower,upper,left,mid);
            int rightCount = countRange(nums,lower,upper,mid+1,right);
            int res = leftCount + rightCount;


            // 假设 前缀和 arr_left 单调递增，arr_right 单调递增，下面先求出 arr_right[r] -arr_left[l] 在区间[lower，upper]的个数

            int index = left;
            int l = mid + 1;
            int r = mid + 1;
            /**
             * 此处双指针问题，原使用双重for循环,超出时间限制
             * for (int i =left ; i<=mid; i++) {
             *                 if(nums[right]-nums[i] < lower ){
             *                     break;
             *                 }
             *                 for (int j =mid +1 ; j<=right ; j++) {
             *                     if(nums[j] -nums[mid] > upper){
             *                         break;
             *                     }
             *                     if(nums[j] - nums[i] >= lower && nums[j] -nums[i] <= upper){
             *                         res =res +1;
             *                     }
             *                 }
             * }
             */
            while (index <= mid) {
                // l 为小于 lower的数量， r为<=upper的数量，差集个数为在[lower,upper]的个数
                while (l <= right && nums[l] - nums[index] < lower) l++;
                while (r <= right && nums[r] - nums[index] <= upper) r++;
                res = res + (r - l);
                index++;
            }
            //合并left & right数组，使其单调递增
            long[] sorted = new long[right -left +1];
            l = left;
            r = mid+1;
            int sortedArrIndex = 0;
            while(l <= mid || r <= right) {
                if(l > mid) {
                    sorted[sortedArrIndex ++] = nums[r++];
                }else if( r > right) {
                    sorted[sortedArrIndex ++] = nums[l++];
                }else{
                    if(nums[l] < nums[r]){
                        sorted[sortedArrIndex++] = nums[l++];
                    }else {
                        sorted[sortedArrIndex++] = nums[r++];
                    }
                }
            }
            for(int i =0 ; i<right -left +1 ;i++){
                nums[i+left] =sorted[i];
            }
            return res;
        }
    }

}
